package com.atguigu.linkedlist;

/*
    给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false
    输入：head = [1,2,2,1]
    输出：true
    解题思路：先使用快慢指针找到链表中点，再把链表切成两半；然后把后半段翻转；最后比较两半是否
    相等。
*/
public class PalindromeLinkedList {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return  true ;
        }
        ListNode fast = head, slow = head;
        while (fast.next != null && fast.next.next != null) {
            //快慢指针找出链表中点
            slow = slow.next ;
            fast = fast.next.next ; //循环完慢指针指向即为链表中点
        }
        slow.next = reverseLinkedList(slow.next) ;
        slow = slow.next ;
        while (slow != null) { //链表前半段head与后半段slow逐一比较
            if (head.val != slow.val) {
                return false ;
            }
            head = head.next ;
            slow = slow.next ;
        }
        return true ;
    }


    //反转链表的子函数
    public ListNode reverseLinkedList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode tmp = null;
        while (cur != null) {
            tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
}
